Summary
PHASE6 has created clusters and some egress nodes of each clusters have been linked to ingress node of nearby clusters.
Objectives of this phase are to:
STEP11l1: Linking tip nodes of traversal clusters (populating the table: traversal_tip_connector_highorder2)
Linking tip nodes will enable routing to happen within cluster for any ingress tip node to reach any egress node.
Hence the reachability to any ingress node is ensured of reachability to nearby clusters and hence the overall reachability across the graph is ensured.
Config Params:
dijkstraL2NodeCacheSize is set to 2 million entries so that Dijkstra can run faster
traversalClusterPerTipMaxNodes is 12 (on PROD) 10 (on DEV) based on above COUNT/CARDINALITY analysis
traversalClusterPerTipDistanceCapKm of 10.0 means that only the ingress/egress tip nodes closer than 10km are linked (some nodes are as far away as 50km away)
clusterEdgeFetchBatchSize is 1000 since linking traversal cluster tips is slow
Clusters with from/to nodes > traversalClusterTipMegaClusterNodes will be handled separately below. Set this similar to "nodesInMegaClusters"
traversalClusterTipLocationGrpCap helps hadling mega-cluster query condition (30.0 means nodes within 3-to-5km are taken to check traversalClusterPerTipDistanceCapKm)
persistSecondaryCacheNodes is increased (from 2MB to 3MB) -- so that subsequent batches would take less time to ramp-up
WARNING start from-nodes linking first -- as it truncates the table at the first round.
NOTE:
It runs for 15days. .
from-nodes linking takes longer time -- since we are including (at fill-up stage) lots of contracted-link edge-nodes to the from-node part of the cluster
Link to-nodes of traversal clusters:
nohup ${PCH_APP_HOME}/run_G2KTraversalClusterTipConnector.sh --action buildTraversalClusterToNodesTipConnectorHighOrder2 --forMegaClusters false > $PCH_LOG_HOME/nohup.out 2>&1 &
WARNING do NOT start fromNode linking after to-nodes -- as fromNode task truncates the table at the first round.
NOTE:
The process runs for 5days
SELECT COUNT(tip.*) FROM traversal_tip_connector_highorder2 AS tip;
Results: <<659591637>>
On PROD:
<<659591637>>
Remove very long tip-connectors:
Since typical cluster is < 20km long, we will remove tip-connectors longer than 20km
SELECT link_edge_id,distance FROM traversal_tip_connector_highorder2 WHERE distance >= 0.2 ORDER BY distance DESC;
<<144>>
DELETE FROM traversal_tip_connector_highorder2 WHERE distance >= 0.2;
<<DELETE: 144>>
STEP11m: Including traversal_tip_connector to 2nd level nodes/edges
For comparison below
SET statement_timeout=3600000;
SELECT MIN(CASE WHEN edges_from_ids IS NULL THEN 0 ELSE cardinality(edges_from_ids) END), MAX(cardinality(edges_from_ids)), MIN(CASE WHEN edges_to_ids IS NULL THEN 0 ELSE cardinality(edges_to_ids) END), MAX(cardinality(edges_to_ids)) FROM node_highorder2;
min | max | min | max
-----+-----+-----+-----
0 | 787 | 0 | 785
SET statement_timeout = 9600000; SET lock_timeout=1200000; SET work_mem TO '2048MB';
\set for_tip_conn true
SELECT 2 AS percentile_step, 15000 AS loop_step \gset
CALL g2k_enhance_graph_by_traversal_cluster_tips_highorder2(0, 20, :for_tip_conn, :percentile_step, :loop_step, true);
CALL g2k_enhance_graph_by_traversal_cluster_tips_highorder2(20, 40, :for_tip_conn, :percentile_step, :loop_step, true);
CALL g2k_enhance_graph_by_traversal_cluster_tips_highorder2(40, 60, :for_tip_conn, :percentile_step, :loop_step, true);
CALL g2k_enhance_graph_by_traversal_cluster_tips_highorder2(60, 80, :for_tip_conn, :percentile_step, :loop_step, true);
CALL g2k_enhance_graph_by_traversal_cluster_tips_highorder2(80, 100, :for_tip_conn, :percentile_step, :loop_step, true);
NOTE:
Set for_tip_conn to true for adding for_nodes and to_nodes tip connectors
You may NOT parallelize the above calls with very few multiple sessions -- as node_highorder2 could cause lock errors
Comparing graph improvements
SELECT MIN(CASE WHEN edges_from_ids IS NULL THEN 0 ELSE cardinality(edges_from_ids) END), MAX(cardinality(edges_from_ids)), MIN(CASE WHEN edges_to_ids IS NULL THEN 0 ELSE cardinality(edges_to_ids) END), MAX(cardinality(edges_to_ids)) FROM node_highorder2;
min | max | min | max
-----+-----+-----+-----
0 | 808 | 0 | 790
<<Should be more or same to before>>
STEP11n: Check reachability
nohup ${PCH_APP_HOME}/run_G2KGraphAnalyzer.sh --action graphAnalyzerCheckNodeReachabilityHighOrder2 --randomSeed 12345 > $PCH_LOG_HOME/nohup.out 2>&1 &
This will pick random nodes and reach all other nodes in forward and backward directions.
All random nodes should be able to cover entire graph (fully reachable to everyone)
[G2KGraphAnalyzer] checkGraphReachability: Total forward nodes that could reach all nodes: 0 maxReachablePct: 0.256% minReachablePct: 0.000% out of 10 tries
[G2KGraphAnalyzer] checkGraphReachability: Total backward nodes that could reach all nodes: 0 maxReachablePct: 0.489% minReachablePct: 0.000% out of 10 tries
[G2KGraphAnalyzer] checkGraphReachability: Total nodes that could reach all nodes: 0 maxReachablePct: 0.489% minReachablePct: 0.000% out of 10 tries
NOTE: Max reachability is 0.256% forward and 0.489% backward
~~~~~ Take FULL DB backup ~~~~~
NOTE: full database backup is taken at this point since the next few steps are long and config-dependent. You may want to rollback to this backup to correct config mistakes
STEP12a: Build traversal intra-cluster cross links (populating the table: traversal_cluster_cross_links_highorder2)
This step links through cluster in such a way that all the ingress traversal cluster links are linked to the egress traversal cluster links
Hence, entire graph could be navigated in high-order graph by traversing through traversal cluster links and traversal cluster cross-links
WITH cluster_box AS (
SELECT cluster_id,ST_MaxDistance( from_to_box, from_to_box) AS max_dist FROM traversal_clusters_geom_highorder2
)
SELECT COUNT(max_dist) FROM cluster_box WHERE max_dist < 0.03;
Results: count ------- 231742/295515 (for 0.03) 215139/295515 (for 0.02) 165330/295515 (for 0.01)
Results:
count
-------
231742/295515 (for 0.03) 215139/295515 (for 0.02) 165330/295515 (for 0.01)NOTE: ~78.00% of cluster-gerometry is within 3km, 72.89% within 2km size and 66.85% within 1km
WITH cluster_box AS (
SELECT cluster_id,ST_MaxDistance( from_to_box, from_to_box) AS max_dist FROM traversal_clusters_geom_highorder2
)
SELECT MAX(max_dist) FROM cluster_box;
max
------------------
0.23954448155192024
NOTE: Largest cluster-gerometry is ~23.95km size
WITH cluster_box AS (
SELECT cluster_id,ST_MaxDistance( from_to_box, from_to_box) AS max_dist FROM traversal_clusters_geom_highorder2
)
SELECT COUNT(max_dist) FROM cluster_box WHERE max_dist > 0.1;
count
-------
27401
NOTE: Only 27401/295515 9.26% cluster-gerometries are larger than 10km size
Config Params:
Since 75% of cluster-gerometry is within 3KM size, exactToClosestPathDistanceTolerancePct is chosen to be 35.0 (10.0 more to reduce "No Solution" results) and expandTraversalClusterGeomBy to be 0.03 (3km)
Otherwise, ~40% of links are no-solution (-4) links -- requiring full cross-link connects later.
exactToClosestPathCostTolerancePct: When closest soln is cheaper by this pct to solution than the acceptable limit, accept the closest -- instead of exact one
closestWithoutExactPathDistanceTolerancePct: When closest inexact soln is closer to solution nodes within the acceptable tolerance%, then accept it
exactToClosestEdgeDistanceRatio and exactToClosestEdgePathCostRatio are unused
nodeRefCacheSize is set to 500000 -- since node ref is repeatedly used for geolocations for closest (not complete) shortest path
(250000 gives close to two-to-one ratio of cache hit-to-fault ratio and lesser node refs are evicted than hit)
graphDBFetchNodeBatchSize is increased to 1000 (from 500) -- since each cluster has large number of from-and-to nodes
nohup ${PCH_APP_HOME}/run_G2KTraversalClusterCrossLinker.sh --action buildTraversalClusterCrossLinkHighOrder2 --forMegaClusters false > $PCH_LOG_HOME/nohup.out 2>&1 &
NOTE:
The script will run for ten batches of 10 percentile each
Each batch runs for ~45min/batch of 10%. For 100 percentile the process runs for ~3days creating 227010 cross-links
Config Params:
executorThreads is reduced to 16 (from 32) -- as mega-clusters are crushing CPU
nohup ${PCH_APP_HOME}/run_G2KTraversalClusterCrossLinker.sh --action buildTraversalClusterCrossLinkHighOrder2 --forMegaClusters true > $PCH_LOG_HOME/nohup.out 2>&1 &
NOTE:
It runs for ~10days
SELECT COUNT(*) FROM traversal_cluster_cross_links_highorder2;
Results: <<61981621/19481527>>
Results:
<<61981621/19481527>>
Analyze the links:
SELECT COUNT(*) FROM traversal_cluster_cross_links_highorder2 where solution_type_code < 0;
Results: <<1957913/16277059>>
Results:
<<1957913/16277059>>
NOTE: These are links without quick solution or failures -- requiring cross-link connections
SELECT solution_type_code, COUNT(*) AS count FROM traversal_cluster_cross_links_highorder2 GROUP BY solution_type_code ORDER BY solution_type_code;
solution_type_code: 1 - Complete; 2 - Nearby; 3 - Zero Edge; -4 - No Solution; -5 - Non Optimal Solution; -6 - Missing Ref; -7 - Error
solution_type_code | count
--------------------+----------
-6 | 15277
-4 | 1942636
1 | 45390057
2 | 12728328
3 | 1905323
NOTE: there are very many incomplete (type-code: 2) solutions. Hence non-optimal decision will be changed accordingly below.
STEP12b: Populating traversal_cluster_cross_links distances
SET statement_timeout = 9600000; SET lock_timeout=1200000; SET work_mem TO '2048MB';
NOTE: You may start multiple sessions and parallelize the calls
Analyze
SELECT MIN(distance), MAX(distance) FROM traversal_cluster_cross_links_highorder2;
min | max
-----+-------------------
0 | 0.504898187121194
NOTE: longest of all cluster_cross_link is 50.4km
Updating invalid source-dest and very round-about paths to be recalculated:
We are going to make > 3000% (30.0) non-optimal quick links to be recalculated by intra-cluster link connectors
SELECT 30.0 AS non_optimal_link_beyond_frac, -5 AS non_optimal_soln_type_code \gset
UPDATE traversal_cluster_cross_links_highorder2 AS cedge SET solution_type_code=:non_optimal_soln_type_code FROM (
WITH rel_dist AS (
SELECT lnk.link_edge_id,lnk.solution_type_code, round((lnk.distance / (from_noderef.ref_node_pt <-> to_noderef.ref_node_pt))::numeric, 0) AS dist_frac
FROM traversal_cluster_cross_links_highorder2 AS lnk
INNER JOIN node_ref_highorder2 from_noderef ON from_noderef.node_id=lnk.from_node_id
INNER JOIN node_ref_highorder2 to_noderef ON to_noderef.node_id=lnk.to_node_id
WHERE lnk.solution_type_code IN (1,2) AND lnk.distance > 0.0
)
SELECT rel_dist.link_edge_id FROM rel_dist WHERE rel_dist.dist_frac > :non_optimal_link_beyond_frac
) AS non_optimal
WHERE cedge.link_edge_id=non_optimal.link_edge_id;
<<1501/3678>>
SELECT solution_type_code, COUNT(*) AS count FROM traversal_cluster_cross_links_highorder2 GROUP BY solution_type_code ORDER BY solution_type_code;
solution_type_code | count
--------------------+----------
-6 | 15277
-5 | 1501
-4 | 1942636
1 | 45388588
2 | 12728296
3 | 1905323
SELECT COUNT(*) FROM traversal_cluster_cross_links_highorder2 WHERE solution_type_code IN (2,-4,-5, -7);
Results: count ---------- 14672433
Results:
count
----------
14672433
<<These would need partial or complete cross-link connections>>
STEP12e: Build traversal cluster cross-link-connectors (populating the table: traversal_cluster_xlnk_conn_highorder2)
Using first-order nodes-and-edges, this step connects (fills-up) the cross links that either did not have any pathing (NO_SOLUTION) or did not reach to the traversal link's node (NEARBY)
Hence, entire graph could be navigated at high-order by traversing through traversal cluster links, traversal cluster cross-links, and traversal cluster cross-link-connectors
Config Params:
dijkstraL2NodeCacheSize is set to 2 million entries so that Dijkstra can run faster
fetchBatchSize is set to 500 to improve node-cache-hits by working only on nearby (by locationGroup) nodes in a micro-batch
deserializingThreads is reduced to 1 (from 2) -- to avoid too much dead-locks
On over-heating old sever, set nodeAccessPauseMsec to 3
secondaryCacheNodeSize can be increased well -- as this task is going to be search-only and forward-only node-cache.
However, keep in mind that for 'reach outs' tasks, a 1/4 secondaryCacheNodeSize highorder cache is created internally. So decide the size properly to avoid OOM error.
If CPU is thrashing with fast Dijkstra calls, reduce secondaryCacheNodeSize -- so that more DB fetches would yield CPU to cool
Alternatively, run server with powersave governor: "cpupower frequency-set --governor powersave"
alertEdgesLinkedPctBelow is reduced to 95.0 for PROD -- since there are > 3% unreachable edges at southern India
graphDBTrimNodesToPct/graphDBTrimEdgesToPct are increased (from 88.0) -- so that JVM won't get restarted for 88% free memory
crossLinkReachAgainDistanceCapKm is used to decide if additional 'reach outs' would be done before doing brute-force shortest path connection
crossLinkReachAgainMaxRounds is used to cap maximum number of additional 'reach outs' would be done (to avoid eternal searching)
WARNING start from-nodes linking first -- as it may truncate the table at the first round.
NOTE:
On PROD, process runs for ~7days
To monitor progress: tail -f ${PCH_LOG_HOME}/GangaToKaveri.log | grep "buildTraversalCrossLinkConnectsForRange: completed so far"
nohup ${PCH_APP_HOME}/run_G2KTraversalCrossLinkConnector.sh --action buildTraversalClusterFromNodeCrossLinkConnectHighOrder2 --forMegaClusters true > $PCH_LOG_HOME/nohup.out 2>&1 &
NOTE:
The process runs for ~7days
SELECT COUNT(*) FROM traversal_cluster_xlnk_conn_highorder2;
Results: count ---------- 713039
Results:
count
----------
713039
SELECT connector_type_code,COUNT(*) FROM traversal_cluster_xlnk_conn_highorder2 GROUP BY connector_type_code; -- 1 means start-end, 3: both-end
Results:
connector_type_code | count
---------------------+--------
1 | 247062
3 | 465977
Results:
connector_type_code | count
---------------------+--------
1 | 247062
3 | 465977
SELECT connector_type_code,COUNT(*) FROM traversal_cluster_xlnk_conn_highorder2 WHERE connector_type_code IN (1,3) GROUP BY connector_type_code; -- 1,3 means start-end, both-end
connector_type_code | count
---------------------+--------
1 | 247062
3 | 465977
connector_type_code | count
---------------------+--------
1 | 247062
3 | 465977
nohup ${PCH_APP_HOME}/run_G2KTraversalCrossLinkConnector.sh --action buildTraversalClusterToNodeCrossLinkConnectHighOrder2 --forMegaClusters false > $PCH_LOG_HOME/nohup.out 2>&1 &
NOTE:
It runs for ~4days
nohup ${PCH_APP_HOME}/run_G2KTraversalCrossLinkConnector.sh --action buildTraversalClusterToNodeCrossLinkConnectHighOrder2 --forMegaClusters true > $PCH_LOG_HOME/nohup.out 2>&1 &
NOTE:
If many incomplete (type-code: 2) solutions need to be found they mostly will run on this to-node linking stage -- taking lots of time
It runs for ~6days
SELECT COUNT(*) FROM traversal_cluster_xlnk_conn_highorder2 WHERE connector_type_code = 2;
Results: count -------- 386419
Results:
count
--------
386419
Analyze the links:
SELECT connector_type_code, COUNT(*) AS count FROM traversal_cluster_xlnk_conn_highorder2 GROUP BY connector_type_code ORDER BY connector_type_code;
Results:
connector_type_code | count
---------------------+--------
1 | 247062
2 | 386419
3 | 465977
Results:
connector_type_code | count
---------------------+--------
1 | 247062
2 | 386419
3 | 465977
NOTE:
connector_type_code < 0 should be very less (< 0.0001%)
connector_type_code = 3 means connecting at both (source and dest) ends (1 and 2)
SELECT MIN(distance), MAX(distance) FROM traversal_cluster_xlnk_conn_highorder2;
On PROD: min | max -----+------------------- 0 | 1.60981133
Results:
min | max
-----+-------------------
0 | 1.60981133
NOTE:
The longest xlnk_conn is 160.98km which is bad
Bad non-optimal links will get fixed in next step
SELECT COUNT(*) FROM traversal_cluster_xlnk_conn_highorder2 WHERE distance > 0.05;
count
--------
580062
NOTE: 580062/16671566 (3.5%) are > 5km long
SELECT COUNT(*) FROM traversal_cluster_xlnk_conn_highorder2 WHERE distance > 0.1; -- 0.2
count
--------
406585
NOTE: 406585/16671566 (2.43%) are > 10km long
STEP12g: Fixing wildly non-optimal cross-link-connects
If distance of a cross-link-connect is more than 20 times to geographical distance between the points that are connected,
then we will remove those connections and force re-connect them using first-level graph WITHOUT using intermediate reaches.
This will resolve the condition of cross-link-connecting opposite facing (within a cluster) nodes.
Add the non-optimal cross-link-connects to fix-table:
CREATE UNLOGGED TABLE traversal_cluster_xlnk_conn_to_fix AS SELECT xlnkconn.ref_link_edge_id
FROM traversal_cluster_xlnk_conn_highorder2 AS xlnkconn, node_ref_highorder2 AS noderef
WHERE 1=1
AND xlnkconn.distance > :min_xlnk_distance
AND (xlnkconn.distance/ST_Distance(xlnkconn.from_node_pt, xlnkconn.to_node_pt)) >= :geo_to_lnk_dist_ratio
AND noderef.node_id=xlnkconn.from_node_id
ORDER BY noderef.location_grp;
<<INSERT: 13987>>
Remove the non-optimal cross-link-connects:
DELETE FROM traversal_cluster_xlnk_conn_highorder2 WHERE ref_link_edge_id IN (
SELECT ref_link_edge_id FROM traversal_cluster_xlnk_conn_to_fix
);
Manually re-run cross-link-connects for from-nodes without intermediate reaches:
nohup ${PCH_APP_HOME}/run_G2KTraversalCrossLinkConnector.sh --action buildTraversalClusterFromNodeCrossLinkConnectHighOrder2 --fixIssues true --skipTruncate true
--forceConnectWithoutReach true --yesIReallyWantToDo true --tablespec traversal_cluster_xlnk_conn_to_fix > $PCH_LOG_HOME/nohup.out 2>&1 &
NOTE:
forceConnectWithoutReach is set to true
fixIssues is set to true
It runs for 8hrs
SELECT MIN(distance), MAX(distance) FROM traversal_cluster_xlnk_conn_highorder2;
Results: min | max -----+-------------------- 0 | 0.014384274144041862
Results:
min | max
-----+--------------------
0 | 1.4384274144041862
NOTE: longest xlnk_conn is 1.4384km
The longest distance should be lesser than what we got in STEP12f
STEP12i: Load traversal cluster links based cluster_node/cluster_edge
IMPORTANT Preserve this. The cluster-nodes/edges are going to be used by routing services and for interior links connecting cluster
SET statement_timeout = 9600000; SET lock_timeout=1200000; SET work_mem TO '2048MB';
INSERT INTO cluster_edge (edge_id, source_data_edge_id, edge_cost, distance, access_only, from_node_id, to_node_id)
SELECT link_edge_id, link_edge_id, edge_cost, distance, false, from_cluster_id, to_cluster_id FROM traversal_cluster_links_highorder2;
Results: <<3556568>>
Results:
<<3556568>>
INSERT INTO cluster_node (node_id,barrier,contraction_allowed,contraction_order,edges_from_ids,edges_to_ids,cluster_id)
WITH forward_edges AS (
SELECT from_cluster_id AS cluster_id, array_agg(link_edge_id) AS edges_from_ids FROM traversal_cluster_links_highorder2 GROUP BY from_cluster_id
), backward_edges AS (
SELECT to_cluster_id AS cluster_id, array_agg(link_edge_id) AS edges_to_ids FROM traversal_cluster_links_highorder2 GROUP BY to_cluster_id
)
SELECT CASE WHEN forward_edges.cluster_id IS NOT NULL THEN forward_edges.cluster_id ELSE backward_edges.cluster_id END, false, true, 9223372036854775807,
forward_edges.edges_from_ids, backward_edges.edges_to_ids,
CASE WHEN forward_edges.cluster_id IS NOT NULL THEN forward_edges.cluster_id ELSE backward_edges.cluster_id END
FROM forward_edges FULL OUTER JOIN backward_edges ON forward_edges.cluster_id = backward_edges.cluster_id;
Results: <<295225>>
Results:
<<295225>>
WARNING The cluster-node count (295225) should be very close to total traversal clusters (295515) 99.9%
STEP12j: Verify reachability of traversal cluster links based cluster_node
Verify all cluster nodes have some out/in edges/links:
Check Cluster-node reachability:
nohup ${PCH_APP_HOME}/run_G2KGraphAnalyzer.sh --action graphAnalyzerCheckClusterReachability --randomSeed 12345 > $PCH_LOG_HOME/nohup.out 2>&1 &
%PCH_APP_HOME%\run_G2KGraphAnalyzer.cmd --action graphAnalyzerCheckClusterReachability --randomSeed 12345 --paginationspec C:\GangaToKaveri\data\runtime_cost_spec_by_db.json
This will pick random nodes and reach all other nodes in forward and backward directions.
All random nodes should be able to cover entire graph (fully reachable to everyone)
2025-02-15 23:59:19,414 INFO main [G2KGraphAnalyzer] checkGraphReachability: Total forward nodes that could reach all nodes: 5 maxReachablePct: 99.873% minReachablePct: 99.873% out of 10 tries
2025-02-15 23:59:25,771 INFO main [G2KGraphAnalyzer] checkGraphReachability: Total backward nodes that could reach all nodes: 10 maxReachablePct: 99.901% minReachablePct: 99.901% out of 10 tries
2025-02-15 23:59:25,771 INFO main [G2KGraphAnalyzer] checkGraphReachability: Total nodes that could reach all nodes: 10 maxReachablePct: 99.901% minReachablePct: 99.901% out of 10 tries
NOTE:
Max reachability is 99.87% forward and 99.9% backward
If graph is not fully reachable or not reachable percent is less than 90%:
Increase nearestClusteredShortcutsToLink and redo.
STEP12m: Backup
~~~~~ Take incremental DB backup ~~~~~